#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

void PreorderTraversal( BinTree BT ); /* 先序遍历，由裁判实现，细节不表 */
void InorderTraversal( BinTree BT );  /* 中序遍历，由裁判实现，细节不表 */

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );
BinTree FindFather( BinTree BST, ElementType X );

int main()
{
    BinTree BST, MinP, MaxP, Tmp;
    ElementType X;
    int N, i;

    BST = NULL;
    scanf("%d", &N);
    for ( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Insert(BST, X);
    }
    printf("Preorder:"); PreorderTraversal(BST); printf("\n");
    MinP = FindMin(BST);
    MaxP = FindMax(BST);
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        Tmp = Find(BST, X);
        if (Tmp == NULL) printf("%d is not found\n", X);
        else {
            printf("%d is found\n", Tmp->Data);
            if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
            if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
        }
    }
    scanf("%d", &N);
//printf("N:%d\n",N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Delete(BST, X);
    }
	//if(BST == NULL)printf("fuck\n");
    printf("Inorder:"); InorderTraversal(BST); printf("\n");

    return 0;
}
/* 你的代码将被嵌在这里 */
BinTree Insert( BinTree BST, ElementType X ){
	BinTree ret=BST;
	BinTree *link=&ret;
	while( BST ){
		if( X <= BST->Data ){
			link=&(BST->Left);
			BST=BST->Left;
		}else{
			link=&(BST->Right);
			BST=BST->Right;
		}
	}
	BinTree new=malloc(sizeof(struct TNode));
	new->Data=X;
	new->Left=new->Right=NULL;
	*link=new;
	return ret;
}
BinTree Delete( BinTree BST, ElementType X ){
	BinTree child=BST;
	BinTree *father=&BST;
	while( child && (X!=child->Data) ){
		if( X < child->Data ){
			father=&(child->Left);
			child=child->Left;
		}
		else{
			father=&(child->Right);
			child=child->Right;
		}
	}
	if(!child){printf("Not Found\n");return BST;}
	BinTree r;
	//if( r=FindMax(child->Left) ){
		//BinTree f=FindFather(BST,r->Data);
		//child->Data=r->Data;
		//f->Right=r->Left;
		//free(r);
	//}
	//}else if( r=FindMin(child->Right) ){
	//	BinTree f=FindFather(BST,r->Data);
	//	child->Data=r->Data;
	//	f->Left=r->Right;
	//	free(r);
	if( child->Left && !child->Right ){
		*father=child->Left;
		free(child);
	}else if( child->Right && !child->Left ){
		*father=child->Right;
		free(child);
	}else if( child->Right && child->Left ){
		if( !(child->Left->Right) ){
			child->Data=child->Left->Data;
			BinTree tmp=child->Left;
			free(tmp);
			child->Left=child->Left->Left;
		}else{
			r=FindMax(child->Left);
			BinTree f=FindFather(BST,r->Data);
			child->Data=r->Data;
			f->Right=r->Left;
			free(r);
		}
	}else{
		free(child);
		*father=NULL;
	}
	return BST;
}

BinTree FindFather( BinTree BST, ElementType X ){
	BinTree father,child;
	child=BST;
	father=NULL;
	while( child && child->Data!=X ){
		if( X < child->Data ){
			father=child;
			child=child->Left;
		}else{
			father=child;
			child=child->Right;
		}
	}
	return father;
}
Position Find( BinTree BST, ElementType X ){
	while( BST && (X!=BST->Data) ){
		if( X < BST->Data )BST=BST->Left;
		else	BST=BST->Right;
	}
	if(!BST)
		return NULL;
	else
		return BST;
}
Position FindMin( BinTree BST ){
	if(!BST)return NULL;
	while(BST->Left){
		BST=BST->Left;
	}
	return BST;
}
Position FindMax( BinTree BST ){
	if(!BST)return NULL;
	while(BST->Right){
		BST=BST->Right;
	}
	return BST;
}
void PreorderTraversal( BinTree BT ){
	if(NULL==BT)return;
	//printf("%d-",BT->Data);
	PreorderTraversal(BT->Left);
	PreorderTraversal(BT->Right);
	return;
}
void InorderTraversal( BinTree BT ){
	if(NULL==BT)return;
	InorderTraversal(BT->Left);
	//printf("%d-",BT->Data);
	InorderTraversal(BT->Right);
	return;
}
